8.4.4. İkili Arama Ağacından Düğüm Silme Algoritması

İkili arama ağacından düğüm silme üzerinde durulması gereken bir durumdur; hem tüm kritik durumlar gözönüne alınmalı, hem ağacın dengesi çok bozulmamalı, hem de ikili arama ağacı özelliği korunmalıdır. Genel olarak bir ağaçtan düğüm silinirken/çıkarılırken 3 durumdan birisiyle karşılaşılır. Silinecek düğüm,

•  Şekilde b)'de görüldüğü gibi yaprak düğüm olabilir; bu durumda onun ailesindeki işaretçi alanına NULL yerleştirilir ya da,
•  c)'de görüldüğü gibi yalnızca bir tarafında altağaç olabilir; bu durumda o altağacın bağlantısı çıkarılacak düğümün ailesindeki işaretçi alanına yerleştirilir ya da,
•  d)'de görüldüğü gibi çıkarılacak düğümün iki tarafında da altağaç olabilir. Yani iki tane çocuğu da vardır. Bu durumda sol altağaç, sağ altağacın en küçük düğümünün soluna eklenir.

Ekleme için gerekli bağlantıları yapıldıktan sonra çıkarılan düğümün işgal ettiği bellek alanı serbest bırakılmalıdır. Eğer, ağaç kurulurken malloc() benzeri bir fonksiyonla dinamik bellek alanı alınmışsa free() fonksiyonu kullanılır. Şekilde d)'de görüleceği gibi silinecek düğümün iki çocuğu da varsa, yani ona bağlı iki altağaç varsa, soldaki altağaç sağdaki altağacın en küçük değere sahip düğümün soluna eklenmektedir.

Bir önceki silme yönteminde, eğer silinecek düğümün iki çocuğu da varsa, yani ona bağlı iki altağaç varsa, soldaki altağaç sağdaki altağacın en küçük değere sahip düğümün soluna eklenmektedir. Bu durum, özellikle çok fazla silinmelerin yapıldığı uygulamalarda ağacın dengeli olmasını bozup ağacın tek yönde, bağlantılı liste gibi büyümesine neden olabilir. Böylesi durumlarda, zaman maliyeti biraz artsa da dengeli silme yapan algoritma kullanılmalıdır. Böyle bir algoritmanın davranışı şekilde verildiği gibi olabilir.

Aşağıda silinecek düğümü en fazla bir çocuklu hale getiren bir silme algoritmasının kaba-kodu verilmiştir:

İkili arama ağacından düğüm silme/çıkartma algoritması kaba-kodu

while(silinecek düğümün ve ailesinin adresini bulana kadar)      q <- silinecek düğümün, qa<- ailesinin adresi; if(silinmek istenen bulunamadı ise)      yapacak birşey yok dön; if(silinecek düğümüm iki alt çocuğu da varsa)      sol alt ağacın en büyük değerli düğümünü bul;      bu düğümdeki bilgiyi silinmek istenen düğüme aktar; bu aşamada en fazla bir çocuğu olan düğümü sil; silinen düğümün işgal ettiği bellek alanını serbest bırak; }